This invention relates to communications systems; more particularly, the invention relates to resequencing packets in packet switching systems that use interconnection networks in which packets going to any single output link may leave the interconnection network in a different order than that in which they entered. The invention provides a way of resequencing packets at output ports of an interconnection network, without the possibility of resequencing errors, using packet timestamps and timestamp floors; timestamp floors provide a bound on the timestamps of packets that can be received in the future at a particular interconnection network output.
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology.
As used herein, the term xe2x80x9cpacketxe2x80x9d refers to packets of all types, including, but not limited to, fixed length cells and variable length packets. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. Furthermore, the term xe2x80x9csystemxe2x80x9d is used generically herein to describe any number of components, packet switch elements, packet switches, networks, computer and/or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire high reliability and increased performance at a reasonable price. A commonly used technique for helping to achieve this goal is for these systems to provide multiple paths between a source and a destination. Packets of information are then dynamically routed and distributed among these multiple paths. It is typically more cost-effective to provide multiple slower rate links or switching paths than to provide a single higher rate path. Such designs also achieve other desired performance characteristics.
Buffered multistage interconnection networks are often used in Asynchronous Transfer Mode (xe2x80x9cATMxe2x80x9d) and others types of packet switching systems. Networks of this type use internal buffers to store packets at intermediate points when contention for output links prevents their immediate transmission.
Many multistage interconnection networks provide multiple paths between network inputs and outputs, allowing the traffic to be balanced across the alternative paths. An example of such a network 100 is shown in FIG. 1. This particular network is known as a three stage Beneg network. The network is composed of switch elements (SE""s) and interconnecting links. SE""s may have any number of input links and output links. The value d denotes the number of input links and the number of output links in a single SE and the value n denotes the number of input links and output links of the multistage network. Network 100 as shown in FIG. 1, has a d value of 4 and an n value of 16.
Traffic distribution in multistage networks is commonly done in one of two ways. In systems that use static routing, all packets associated with a given end-to-end session (in ATM networks, a session will typically be associated with a virtual circuit), follow the same path through the interconnection network. This path is selected when the session begins and typically remains fixed until the session is completed.
In systems that use dynamic routing, traffic is distributed on a packet-by-packet basis so as to equalize the traffic load across the entire interconnection network. Dynamic routing systems distribute traffic more evenly than systems that use static routing and consequently can be operated with lower speed internal links than are needed for systems that use static routing. However, because dynamic routing systems do not constrain the packets belonging to a single user session to a single path, they may allow packets in a given session to become out of order.
Systems using dynamic routing typically provide resequencing mechanisms to restore the correct packet order at the outputs of the switching system. Conventional mechanisms for resequencing usually ensure that packets are delivered in the correct order, but under unusual conditions, they can fail to reorder packets correctly.
A common method for resequencing packets in a multistage interconnection network uses timestamps and time-ordered output queues. Such systems have a central timing reference, which is distributed to the circuits at all inputs to the network and to the circuits at all outputs. When a packet enters the network at an input, the current time is inserted into a field in the packet. When the packet emerges from the network at the appropriate destination, the timestamp is used to insert the packet into a time-ordered queue. That is, packets are read from the queue in increasing order of their timestamp values. Associated with the queue is an age threshold which specifies the minimum time that must elapse between the time a packet entered the interconnection network until it is allowed to leave the resequencing buffer at the output. If the difference between the current time and the timestamp of the first packet in the buffer is smaller than the age threshold, then the first packet is held back (along with all others xe2x80x9cbehindxe2x80x9d it in the buffer). This allows packets that are delayed for a long period of time in the interconnection network to catch up with other packets that experience smaller delays.
If the age threshold is larger than the maximum delay that packets ever experience in the interconnection network, then the time-based resequencing algorithm will always deliver packets in order. However, if packets are delayed by more than the time specified by the age threshold, errors may occur. In typical systems, delays in the interconnection network are usually fairly small (a few packet times per stage) and packets only rarely experience long delays. On the other hand, the worst-case delay may be very large. As a result, the age threshold is usually set not to the worst-case delay, but to a smaller value chosen to give an acceptably small frequency of resequencing errors. One can trade-off the resequencing delay for reduced probability of resequencing errors. Conventional time-based resequencing method can be implemented in various ways.
Because resequencing errors can cause errors in delivered data, leading to lost data or the need to retransmit data, it is advantageous to reduce or eliminate resequencing errors. Consequently, needed are new methods and apparatus for resequencing packets, so as to reduce or eliminate resequencing errors.
One embodiment of a packet switching system that employs the invention, includes an interconnection network that is used to provide communication from a set of input port circuits to a set of output port circuits. The input port circuits add a timestamp field to packets as they are sent to the interconnection network. The interconnection network contains switch elements that include circuits that maintain information about timestamp floors. A timestamp floor is a bound on the earliest timestamp values that can appear in packets that will arrive in the future. The interconnection network propagates timestamp floors to resequencers, typically located in the output port circuits, which use the timestamp floors to determine when packets can be forwarded on their outgoing links, without the possibility of resequencing errors.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.